package com.cat.binaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/cousins-in-binary-tree-ii/description/
 * @create 2025/9/29 18:52
 * @since JDK17
 */

public class Solution91 {
    class Info {
        TreeNode node, father;
        public Info(TreeNode node, TreeNode father) {
            this.node = node;
            this.father = father;
        }
    }

    public TreeNode replaceValueInTree(TreeNode root) {
        Deque<Info> q = new ArrayDeque<>();
        q.add(new Info(root, root));
        while (!q.isEmpty()) {
            int n = q.size(), sum = 0;
            List<Info> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                var info = q.poll();
                var x = info.node;
                sum += x.val;
                list.add(info);
                if (x.left != null) {
                    q.add(new Info(x.left, x));
                }
                if (x.right != null) {
                    q.add(new Info(x.right, x));
                }
            }
            for (int i = 0; i < n; i++) {
                var cur = list.get(i);
                int left = i > 0 && list.get(i - 1).father == cur.father ? list.get(i - 1).node.val : 0;
                int right = i < n - 1 && list.get(i + 1).father == cur.father ? list.get(i + 1).node.val : 0;
                cur.node.val = sum - cur.node.val - left - right;
            }
        }
        return root;
    }
}
